/*
平均时间复杂度：O(logn)， 具有 n 个节点的二叉树的高度不会超过log2(n) + 1
空间复杂度为 O(1)

根据每次比较的节点，生成一个判定树
比较次数 = 路径上的节点数 = 节点的层数 = 树的深度
比较不成功：平均时间复杂度 log2(n) + 1
*/
#include <stdio.h>

// 折半查找函数
int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2;  // 避免溢出的计算中间位置的方法

        if (arr[mid] == key) {
            return mid;  // 找到关键字，返回其位置
        } else if (arr[mid] < key) {
            low = mid + 1;  // 关键字在中间位置的右侧
        } else {
            high = mid - 1;  // 关键字在中间位置的左侧
        }
    }
    return -1;  // 如果没有找到关键字，返回-1
}

// 主函数，用于测试折半查找
int main() {
    int data[] = {3, 5, 8, 10, 14, 17, 21, 24, 27, 30, 33};  // 一个已排序的数组
    int size = sizeof(data) / sizeof(data[0]);
    int key = 10;  // 我们想要查找的关键字

    int index = binarySearch(data, 0, size - 1, key);  // 调用折半查找函数

    if (index != -1) {
        printf("Element found at index: %d\n", index);
    } else {
        printf("Element not found.\n");
    }

    return 0;
}
